package offer;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class offerII_0074 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        LinkedList<int[]> list=new LinkedList<>();
        int len=intervals.length;
        list.add(intervals[0]);
        for(int i=1;i<len;++i){
            if(list.getLast()[1]>=intervals[i][0]){
                int[] tmp=list.removeLast();
                tmp[1]=Math.max(tmp[1],intervals[i][1]);
                list.add(tmp);
            }
            else{
                list.add(intervals[i]);
            }
        }
        len=list.size();
        int[][] result=new int[len][2];
        for(int i=0;i<len;++i){
            result[i]=list.removeFirst();
        }
        return result;
    }
}
